import random
import copy
from blackbox import Point
from blackbox import BlackBox
from climbing import HillClimbing

import matplotlib.pyplot as plt

def createOffspringDiscrete(parent1, parent2, solutionSize):
	solution = Solution([0 for x in range(0, solutionSize)])
	for index in range(0, solutionSize):
		if random.randint(0,1) == 0:
			solution.pointsList[index] = parent1.pointsList[index]
		else:
			solution.pointsList[index] = parent2.pointsList[index]
	return solution

def createOffspringMean(parent1, parent2, solutionSize):
	solution = Solution([0 for x in range(0, solutionSize)])
	for index in range(0, solutionSize):
		solution.pointsList[index] =  Point((parent1.pointsList[index]).x, ((parent1.pointsList[index]).y + (parent2.pointsList[index]).y)  /2)
	return solution

def listToString(list):
	listString = '['
	listLength = len(list)
	if listLength <= 0:
		return '[]'
	for index, element in enumerate(list):
		listString += element.__str__()
		if index < listLength - 1:
			listString += ', '
	listString += ']'
	return listString

def getSolutionsFitnesses(solutionsList):
		list = []
		for index, solution in enumerate(solutionsList):
			list.append(solution.fitness)
		return listToString(list)

class Solution:
	def __init__(self, pointsList = []):
		self.pointsList = pointsList
		self.fitness = 0
		self.successfulMutations = 0
		self.mutationsTotal = 0
		self.stdDev = 1.0
	
	def __str__(self):
		return 'Solution[fitness: ' + str(self.fitness) + ' ,values:' + listToString(self.pointsList)
	
	def adjustMutationStdDev(self, period):
		if self.mutationsTotal != period:
			return
		if self.successfulMutations/period >= 0.2:
			self.stdDev = self.stdDev * 1.22
		else:
			self.stdDev = self.stdDev * 0.82
		self.successfulMutations = 0
		self.mutationsTotal = 0

class GeneticAlgorithm:
	def __init__(self, solutionSize = 100, populationPollSize = 20, populationGeneartionSize = 100, mutationChance = 1, mutationChange = 1, maxIterations = 2000, mutatedPoints = 5, wthParents = False, adaptive=False, gaussianMutation=False, offspringSelectionMethod=createOffspringMean, recombinate = True, mutationAdjustmentPeriod=5, minimalSoultionQuality=0.0001, qualityLookup=20):
		self.populationPollSize = populationPollSize
		self.populationGeneartionSize = populationGeneartionSize
		self.solutionSize = solutionSize
		self.blackBox = BlackBox()
		self.populationPoll = []
		self.mutationChance = mutationChance
		self.maxIterations = maxIterations
		self.mutationChange = mutationChange
		self.bestSolution = Solution()
		self.bestSolution.fitness = 10000
		self.bestFitnessHistory = []
		self.wthParents = wthParents
		self.mutatedPoints = mutatedPoints
		self.offspringSelectionMethod = offspringSelectionMethod
		self.recombinate = recombinate
		self.adaptive = adaptive
		self.gaussianMutation = gaussianMutation
		self.mutationAdjustmentPeriod = mutationAdjustmentPeriod
		self.minimalSoultionQuality = minimalSoultionQuality
		self.qualityLookup = qualityLookup

	def initializePopulationPopulationPoll(self):
		random.seed()
		populationPoll = [None for x in range(0, self.populationPollSize)]
		for index in range(0, self.populationPollSize):
			populationPoll[index] = self.initializeSolution()
		return populationPoll
	
	def initializeSolution(self):
		interval = 10.0/(self.solutionSize - 1)
		pointsList = []
		pointsList.append(Point(0, 0))
		for index in range (1, self.solutionSize - 1):
			pointsList.append(Point(interval*index, random.uniform(0, 10)))
		pointsList.append(Point(10, 10))
		return Solution(pointsList)
	
	def calculateFitnesses(self, population):
		for index, solution in enumerate(population):
			prevFitness = copy.deepcopy(solution.fitness)
			solution.fitness = self.blackBox.calculateTime(solution.pointsList)
			if (prevFitness > solution.fitness):
				solution.successfulMutations += 1
			solution.mutationsTotal += 1
	
	def optimizePopulation(self, population):
		for index in range(0, self.populationPollSize):
			population[index] = Solution(HillClimbing().optimize(population[index].pointsList))
		return population
		
	def startAlgorithm(self):
		self.populationPoll = self.initializePopulationPopulationPoll()
		self.calculateFitnesses(self.populationPoll)
		self.populationPoll = sorted(self.populationPoll, key=lambda solution: solution.fitness)
		self.bestSolution = self.populationPoll[0]
		self.bestFitnessHistory.append(self.bestSolution.fitness)
		for index in range (0, self.maxIterations):
			if index % 200 == 0:
				print index
			if self.recombinate == True:
				population = self.selectRecombinatedPopulation()
			else:
				population = self.selectPopulation()
			if self.gaussianMutation:
				self.mutatePopulationGaussian(population)
			else:
				self.mutatePopulatiom(population)
			self.populationPoll = self.selectPoll(population)
			if self.adaptive:
				self.updateStdDev(self.populationPoll)
			if self.populationPoll[0].fitness < self.bestSolution.fitness:
				self.bestSolution = self.populationPoll[0]
			self.bestFitnessHistory.append(self.populationPoll[0].fitness)
			
			quality = self.bestSolution.fitness/(index+1)
			if not self.isQualityGood():
				print " Evolutionary algorithm ended at iteration: " + str(index)
				break

	def isQualityGood(self):
		quality = 0;
		if len(self.bestFitnessHistory) < self.qualityLookup:
			return True
		historyLen = len(self.bestFitnessHistory)
		for index in range(historyLen - self.qualityLookup, historyLen - 1):
			quality += abs(self.bestFitnessHistory[index] - self.bestFitnessHistory[index+1])
		if quality/self.qualityLookup < self.minimalSoultionQuality:
			print "solution quality : " + str(quality/self.qualityLookup)
			return False
		else:
			return True
	
	def mutatePopulatiom(self, population):
		for index, solution in enumerate(population):
			if random.uniform(0, 1) <= self.mutationChance:
				solution.pointsList[random.randint(1, self.solutionSize - 2)].y += random.uniform(-self.mutationChange, self.mutationChange)
	
	def mutatePopulationGaussian(self, population):
		for index, solution in enumerate(population):
			if random.uniform(0, 1) <= self.mutationChance:
				for i in range(0, self.mutatedPoints):
					solution.pointsList[random.randint(1, self.solutionSize - 2)].y += random.gauss(0, solution.stdDev)
	
	def updateStdDev(self, population):
		for index, solution in enumerate(population):
			solution.adjustMutationStdDev(self.mutationAdjustmentPeriod)
	
	def selectPoll(self, population):
		self.calculateFitnesses(population)
		if self.wthParents:
			population.extend(self.populationPoll)
		population = sorted(population, key=lambda solution: solution.fitness)
		return population[0:self.populationPollSize]
	
	def selectPopulation(self):
		population = [None for x in range(0, self.populationGeneartionSize)]
		fitnessSum = self.calculateFitnessSum()
		for index in range (0, self.populationGeneartionSize):
			population[index] = self.chooseGenotypeRoulette(fitnessSum, True)
		return population
	
	def selectRecombinatedPopulation(self):
		population = [None for x in range(0, self.populationGeneartionSize)]
		fitnessSum = self.calculateFitnessSum()
		for index in range (0, self.populationGeneartionSize):
			population[index] = self.createOffspring(fitnessSum)
		return population
	
	def createOffspring(self, fitnessSum):
		parent1 = self.chooseGenotypeRoulette(fitnessSum)
		parent2 = self.chooseGenotypeRoulette(fitnessSum)
		return self.offspringSelectionMethod(parent1, parent2, self.solutionSize)
	
	def chooseGenotypeRoulette(self, fitnessSum, deepCopy=False):
		accumulatedFitness = 0
		randomNumber = random.uniform(0, fitnessSum)
		for index, solution in enumerate(self.populationPoll):
			if accumulatedFitness + solution.fitness >= randomNumber:
				if deepCopy:
					return copy.deepcopy(solution)
				else:
					return solution
			else:
				accumulatedFitness += solution.fitness
	
	def calculateFitnessSum(self):
		sum = 0
		for index, solution in enumerate(self.populationPoll):
			sum += solution.fitness
		return sum

#solutionSize = 100, populationPollSize = 20, populationGeneartionSize = 100, mutationChance = 1, mutationChange = 1, maxIterations = 2000, mutatedPoints = 5, wthParents = False, adaptive=False, solutionSize = 100, gaussianMutation=False, offspringSelectionMethod=createOffspringMean, recombinate = True
alg = GeneticAlgorithm(20, 10, 20, 1, 1, 3000, mutatedPoints=5, wthParents=True, adaptive=True, gaussianMutation=True, recombinate=False, mutationAdjustmentPeriod=5)
alg.startAlgorithm()
print(alg.bestSolution.fitness)
a = HillClimbing().optimize(alg.bestSolution.pointsList)
print(BlackBox().calculateTime(a))

xList = []
yList = []
for index, point in enumerate(a):
	xList.append(point.x)
	yList.append(point.y)

plt.gca().invert_yaxis()
plt.plot(xList, yList)
plt.show()
plt.plot([x for x in range(len(alg.bestFitnessHistory))], alg.bestFitnessHistory)
plt.show()